// 1475. 商品折扣后的最终价格
/**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function (prices) {
	const len = prices.length
	const ans = new Array(len).fill(0)
	for (let i = 0; i < len; i++) {
		let cur = prices[i]
		for (let j = i + 1; j < len; j++) {
			if (prices[j] <= prices[i]) {
				cur = prices[i] - prices[j]
				break
			}
		}
		ans[i] = cur
	}
	return ans
}
/* 单调栈 */
var finalPrices = function (prices) {
	const n = prices.length
	const ans = new Array(n).fill(0)
	const stack = []
	for (let i = n - 1; i >= 0; i--) {
		while (stack.length && stack[stack.length - 1] > prices[i]) {
			stack.pop()
		}
		ans[i] = stack.length ? prices[i] - stack[stack.length - 1] : prices[i]
		stack.push(prices[i])
	}

	return ans
}
finalPrices([10, 1, 1, 6])
